// 给定一个二叉树，我们在树的节点上安装摄像头。
// 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象
// 计算监控树的所有节点所需的最小摄像头数量
// 思路，贪心
// 局部最优：让叶子节点的父节点安装摄像头，摄像头最少，全局最优
// 从叶子节点往上遍历，后序遍历，左右中
// 定义三种状态， 0，无覆盖，1，有摄像头，2，有覆盖，空节点默认为有覆盖，这样不影响叶子节点
// 四类情况：
// 1. 左节点和右节点都有覆盖，返回无覆盖
// 2. 左节点和右节点至少有一个无覆盖，返回摄像头
// 3. 左节点和右节点至少一个有摄像头，返回有覆盖
// 4. 根节点为无覆盖时，结果加1
function minCameraCover(root) {
    // 0, 无覆盖，1，有摄像头，2，有覆盖
    let result = 0
    function dfs(root) {
        // 空节点默认为有覆盖
        if (!root) {
            return 2
        }
        let left = dfs(root.left)
        let right = dfs(root.right)
        if (left === 2 && right === 2) {
            return 0
        }
        if (left === 0 || right === 0) {
            result++
            return 1
        }
        if (left === 1 || right === 1) {
            return 2
        }
    }
    if (dfs(root) === 0) {
        result++
    }
    return result
}